package leetcode;

import java.util.ArrayList;

/**
 * Created by Ghost on 2014/11/3 0003.
 */
public class Convert_Sorted_List_to_Binary_Search_Tree {
    public void leftSide(Integer[] list, int begin, int end, TreeNode father){
        if(end-begin==1){
            father.left = new TreeNode(list[begin]);
        }
        else if(end==begin);
        else{
            int mid = (begin+end)/2;
            father.left = new TreeNode(list[mid]);
            leftSide(list,begin,mid,father.left);
            rightSide(list,mid+1,end,father.left);
        }
    }
    public void rightSide(Integer[] list, int begin, int end, TreeNode father){
        if(end-begin==1){
            father.right = new TreeNode(list[begin]);
        }
        else if(end==begin);
        else{
            int mid = (begin+end)/2;
            father.right = new TreeNode(list[mid]);
            leftSide(list,begin,mid,father.right);
            rightSide(list,mid+1,end,father.right);
        }
    }
    public TreeNode sortedListToBST(ListNode head) {

        if(head==null)
            return null;
        ListNode H = head;
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        int len=0;
        while(H!=null){
            len++;
            arrayList.add(H.val);
            H=H.next;
        }

        if(len==1){
            return new TreeNode(head.val);
        }
        Integer[] list = arrayList.toArray(new Integer[arrayList.size()]);
        int begin = 0,end = list.length;
        int mid = (begin+end)/2;
        TreeNode root = new TreeNode(list[mid]);
        leftSide(list,begin,mid,root);
        rightSide(list,mid+1,end,root);
        return root;
    }
    public static void main(String[] args){
        Convert_Sorted_List_to_Binary_Search_Tree convert_sorted_list_to_binary_search_tree = new Convert_Sorted_List_to_Binary_Search_Tree();
        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        head.next.next.next.next = new ListNode(5);
//        head.next.next.next.next.next = new ListNode(6);
//        head.next.next.next.next.next.next = new ListNode(7);

        TreeNode root = convert_sorted_list_to_binary_search_tree.sortedListToBST(null);

    }
}
